/*https://leetcode.cn/problems/minimize-the-maximum-difference-of-pairs/submissions/562521743/*/

class Solution {  
public:  
    int minimizeMax(vector<int>& nums, int p) {  
        //对数组进行排序 因为下标不影响答案
        sort(nums.begin(), nums.end());  
        int n = nums.size()-1; 
        //在满足条件的情况下，尽可能多的选出下标对 
        function check = [&](int mx) {
            int cnt = 0, i = 0;  
            //在选择下标对的时候，使用到了贪心的思想  
            while (i < n) {
                if (nums[i + 1] - nums[i] <= mx) { 
                    cnt++;  
                    i += 2; // 跳过当前对  
                } else {  
                    i++; // 只移动一个元素
                }  
            }  
            return cnt >= p;  
        };  
        int l = 0, r = nums[n] - nums[0];
        while (l < r) {  
            int mid = l + (r - l) / 2;  
            if (check(mid)) {  
                r = mid; // 更新右边界  
            } else {  
                l = mid + 1; // 更新左边界，确保二分搜索的正确性  
            }  
        }  
        // 循环结束时，l 是满足条件的最小值  
        return l;  
    }  
};